//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 
//
// 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
// 
//
// 示例 2： 
// 
// 
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内 
// -10⁵ <= Node.val <= 10⁵ 
// 
//
// 
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
//
// Related Topics 链表 双指针 分治 排序 归并排序 👍 2199 👎 0

  
package com.tyrone.leetcode.editor.cn;

import java.util.List;

public class SortList{
    public static void main(String[] args) {
       Solution solution = new SortList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /***
     * 归并排序
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        return mergerSort(head);
    }

    private ListNode findMid(ListNode head){
        if (head == null) return head;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode mergerSort(ListNode head){
        if (head == null || head.next == null) return head;
        //找到中间节点
        ListNode mid = findMid(head);
        //排序左右两边：
        // 切割右边
        ListNode right = mid.next;
        mid.next = null;

        ListNode leftHead = mergerSort(head);
        ListNode rightHead = mergerSort(right);
        return merge(leftHead,rightHead);
    }
    //合并两个链表 用一个新的链表表示
    private ListNode merge(ListNode l1,ListNode l2){
        ListNode pre = new ListNode(-1);
        ListNode curr = pre;
        while (l1 !=null &&l2!=null){
            if (l1.val<l2.val){
                curr.next = l1;
                l1=l1.next;
            }else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        //l1或者l2完事了

        if (l1 != null) {
            curr.next = l1;
        }
        if (l2 != null) {
            curr.next = l2;
        }
        return pre.next;
    }

}
//leetcode submit region end(Prohibit modification and deletion)
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
}